﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace eu.h8me.Parsing.LexerLib2 {

    /// <summary>
    /// Helper class describing a range of characters which is stored as an RLE-encoded list of tuples.
    /// </summary>
    internal class CharRange : IEnumerable<Range> {

        /// <summary>
        /// Delegate type which defines a function to process a character range, returning a new range when specified.
        /// </summary>
        /// <param name="range">Range to process.</param>
        /// <returns>Processed replacement range.</returns>
        public delegate CharRange ProcessDelegate(CharRange range);

        // Data.
        private List<Range> _Ranges = new List<Range>();

        /// <summary>
        /// Helper constructor (only internally used) to initialize an empty character range list).
        /// </summary>
        private CharRange() {
            // No specific construction.
        }

        /// <summary>
        /// Initialize a new character range which consists of all characters between start and stop.
        /// </summary>
        /// <param name="start">Range start.</param>
        /// <param name="stop">Range stop.</param>
        public CharRange(char start, char stop) {
            // Attach new range.
            _Ranges.Add(new Range(start, stop));
        }

        /// <summary>
        /// Initialize a character range which contains just one character.
        /// </summary>
        /// <param name="chr">Character to contain.</param>
        public CharRange(char chr) {
            // Attach new range.
            _Ranges.Add(new Range(chr));
        }

        /// <summary>
        /// Initialize a new character range from the existing range object.
        /// </summary>
        /// <param name="range">Range to append to character range object.</param>
        public CharRange(Range range) {
            // Attach present range (is unchangeable.
            _Ranges.Add(range);
        }

        /// <summary>
        /// Group the set of passed ranges, returning an iterator over all possible subranges and containment in the respective
        /// passed ranges.
        /// </summary>
        /// <param name="ranges">Ranges to group.</param>
        /// <returns>Iterator over StateRange objects, which contain information on a grouping.</returns>
        public static IEnumerable<StateRange> GroupRanges(List<CharRange> ranges) {
            // Initialize range listing.
            int[] rangeindexes = new int[ranges.Count];
            bool[] present = new bool[ranges.Count];
            int basebound = Range.MIN_RANGE;
            do {
                // Initialize next value by finding lowest possible bound in the passed ranges.
                int nextbound = Range.MAX_RANGE;
                List<int> statechange = new List<int>();
                for( int i = 0; i < ranges.Count; ++i ) {
                    // Check whether this character range has "run out" of ranges.
                    CharRange range = ranges[i];
                    int rangeindex = rangeindexes[i];
                    if( 2 * range._Ranges.Count == rangeindex )
                        continue;

                    // Test whether we hit a bound.
                    int bound = ( rangeindex & 1 ) != 0 ? range._Ranges[rangeindex >> 1].StopBound : range._Ranges[rangeindex >> 1].StartBound;
                    if( bound < nextbound ) {
                        // This bound is smaller, decrease yield bound (and reset state change set to only contain this).
                        nextbound = bound;
                        statechange.Clear();
                        statechange.Add(i);
                    } else if( bound == nextbound )
                        // This bound is equal, mark as state change (but keep other items that also change bounds).
                        statechange.Add(i);
                }

                // Build state set.
                if( basebound < nextbound )
                    yield return new StateRange(new Range(basebound, nextbound), present);

                // Update state of ranges and set up next iteration.
                basebound = nextbound;
                foreach( int i in statechange ) {
                    // Update present flag to new state (which basically must toggle the flag).
                    Debug.Assert(present[i] == ( ( rangeindexes[i] & 1 ) != 0 ), "Present state does not match index state");
                    present[i] = ( ++rangeindexes[i] & 1 ) != 0;
                }
            } while( basebound != Range.MAX_RANGE );
        }

        /// <summary>
        /// Merge the two character ranges, returning a range which is the unison of the two ranges.
        /// </summary>
        /// <param name="r1">First range to merge.</param>
        /// <param name="r2">Second range to merge.</param>
        /// <returns>Normalized, merge range.</returns>
        public static CharRange operator |(CharRange r1, CharRange r2) {
            // Walk over produced subranges.
            CharRange rv = new CharRange();
            foreach( StateRange range in GroupRanges(new List<CharRange>() { r1, r2 }) ) {
                // Check whether one of the ranges is contained.
                if( range[0] || range[1] ) {
                    // Attach range to rv (but don't add unnecessary ranges at the end).
                    if( rv._Ranges.Count > 0 && rv._Ranges[rv._Ranges.Count - 1].StopBound == range.Range.StartBound )
                        // Merge the ranges, replacing the currently last.
                        rv._Ranges[rv._Ranges.Count - 1] = new Range(rv._Ranges[rv._Ranges.Count - 1].StartBound, range.Range.StopBound);
                    else
                        // Attach range.
                        rv._Ranges.Add(range.Range);
                }
            }

            // Return merged range.
            return rv;
        }

        /// <summary>
        /// Invert the character range, returning a character range that expresses the inverted range.
        /// </summary>
        /// <param name="r">Range to invert.</param>
        /// <returns>Normalized, inverted range.</returns>
        public static CharRange operator !(CharRange r) {
            // Walk ranges, building inverses.
            CharRange rv = new CharRange();
            int lastbound = Range.MIN_RANGE;
            foreach( Range range in r._Ranges ) {
                // Check whether last bound is less, so that we have a new range.
                if( lastbound < range.StartBound )
                    rv._Ranges.Add(new Range(lastbound, range.StartBound));

                // Update last bound.
                lastbound = range.StopBound;
            }

            // Check for final range.
            if( lastbound < Range.MAX_RANGE )
                rv._Ranges.Add(new Range(lastbound, Range.MAX_RANGE));

            // Return result.
            return rv;
        }

        /// <summary>
        /// Return an enumerator over the Ranges contained in this character range.
        /// </summary>
        /// <returns>Typed enumerator over the contained ranges.</returns>
        public IEnumerator<Range> GetEnumerator() {
            // Return enumerator.
            return _Ranges.GetEnumerator();
        }

        /// <summary>
        /// Return an enumerator over the Ranges contained in this character range.
        /// </summary>
        /// <returns>Untyped enumerator over the contained ranges.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Return enumerator.
            return _Ranges.GetEnumerator();
        }

    }

    /// <summary>
    /// Helper class storing an actual character range.
    /// </summary>
    internal class Range {

        // Constants.
        public const int MIN_RANGE = Char.MinValue;
        public const int MAX_RANGE = Char.MaxValue + 1;

        // Data.
        private int _Start;
        private int _Stop;

        /// <summary>
        /// Initialize a new character range which contains the characters between start and stop (inclusive bounds).
        /// </summary>
        /// <param name="start">Range start (inclusive).</param>
        /// <param name="stop">Range stop (inclusive).</param>
        public Range(char start, char stop) {
            // Initialize range.
            _Start = start;
            _Stop = stop + 1;
        }

        /// <summary>
        /// Initialize a new range which contains just the one specified character.
        /// </summary>
        /// <param name="chr">Character to contain.</param>
        public Range(char chr) {
            // Initialize range.
            _Start = chr;
            _Stop = chr + 1;
        }

        /// <summary>
        /// Initialize a new character range which has the explicitly defined bounds set up.
        /// </summary>
        /// <param name="start">Starting bound (inclusive).</param>
        /// <param name="stop">Stopping bound (exclusive).</param>
        public Range(int start, int stop) {
            // Initialize range.
            _Start = start;
            _Stop = stop;
        }

        /// <summary>
        /// Retrieve range start bound to this range.
        /// </summary>
        public char Start {
            get {
                // Return range start.
                return (char)_Start;
            }
        }

        /// <summary>
        /// Retrieve the actual start boundary (inclusive).
        /// </summary>
        public int StartBound {
            get {
                // Return start bound of range.
                return _Start;
            }
        }

        /// <summary>
        /// Retrieve range end bound to this range.
        /// </summary>
        public char Stop {
            get {
                // Return range end.
                return (char)( _Stop - 1 );
            }
        }

        /// <summary>
        /// Retrieve the actual stop boundary (exclusive).
        /// </summary>
        public int StopBound {
            get {
                // Return stop bound of range.
                return _Stop;
            }
        }

    }

    /// <summary>
    /// Helper class used to store a state range.
    /// </summary>
    internal class StateRange {

        // Data.
        private Range _Range;
        private bool[] _States;

        /// <summary>
        /// Initialize a new state range object for the passed range, carrying the respective grouped range states.
        /// </summary>
        /// <param name="range">Range of this subrange.</param>
        /// <param name="states">States of the toplevel ranges.</param>
        public StateRange(Range range, bool[] states) {
            // Store data.
            _Range = range;
            _States = states;
        }

        /// <summary>
        /// Return range this state refers to.
        /// </summary>
        public Range Range {
            get {
                // Return contained range.
                return _Range;
            }
        }

        /// <summary>
        /// Fetch the containment of the respective range in this state.
        /// </summary>
        /// <param name="idx">Index of range to check.</param>
        /// <returns>Boolean indicating whether this range is present in subrange.</returns>
        public bool this[int idx] {
            get {
                // Return range state.
                return _States[idx];
            }
        }

    }

}
